using System;
using System.Collections.Generic;
using System.IO;
using System.Math;
using Nemerle.Utility;
using Nemerle.Collections;

class Task082 : TaskBase
{
  [Record]
  class Item : IComparable[Item]
  {
    mutable public Length : int;
    public Weight : int;
    public Rel : list[int];
    
    override public ToString() : string
    {
      $"($Length, $Weight, $Rel)"
    }
    
    public CompareTo(i : Item) : int
    {
      -Length.CompareTo(i.Length)
    }
  }
  
  override public SolveInt() : int
  {
    def arr = File.ReadAllText("matrix.txt")
      .Split(array[ Environment.NewLine ], StringSplitOptions.RemoveEmptyEntries)
      .Map(s => s.Split(',').Map(int.Parse));
    
    def arrLen = arr.Length;
    
    def getVIndex(i, j)
    {
      i * arrLen + j + 1
    }
    
    def varr = array(arrLen * arrLen + 2);
    arr.IterI(
      (i, x) =>
        x.IterI(
          (j, w) =>
          {
            def lst = [
                (i, j + 1),
                (i + 1, j),
                (i - 1, j)
              ].Filter((x, y) => x >= 0 && x < arrLen && y >= 0 && y < arrLen).Map(getVIndex);
            varr[getVIndex(i, j)] = Item(
              int.MaxValue,
              w,
              if (j == arrLen - 1) (varr.Length - 1) :: lst else lst
            )
          }));
    varr[0] = Item(0, 0, $[ x * arrLen + 1, x in [0..(arrLen - 1)] ]);
    varr[varr.Length - 1] = Item(int.MaxValue, 0, []);
    
    def h = List(varr);
    while (h.Count > 0)
    {
      def f = h.Fold(h[0], (x, a) => if (x.Length < a.Length) x else a);
      h.Remove(f);
      f.Rel.Iter(
        i =>
        {
          def d = varr[i];
          d.Length = Min(d.Length :> long, f.Length :> long + d.Weight) :> int
        })
    }
    
    varr[varr.Length - 1].Length
  }
}
